#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;
class functor_less {
public:
	bool operator()(const int& left, const int& right) {
		return left < right;
	}
};
class functor_greater {
public:
	bool operator()(const int& left, const int& right) {
		return left > right;
	}
};
template<class functor=functor_less>
void MergeSort(int*p,int*tmp, int begin, int end) {
	functor func;
	if (begin >= end) {
		return;
	}
	int mid = (begin + end) / 2;
	MergeSort(p,tmp, begin, mid);
	MergeSort(p,tmp, mid+1, end);

	int s1 = begin;
	int s2 = mid + 1;
	int i =0;
	while (s1 <= mid && s2 <= end)
	{
		if (s1 <= mid && s2 <= end && func(p[s2],p[s1])) {
			tmp[i++] = p[s1++];
		}
		else {
			tmp[i++] = p[s2++];
		}
	}
	while (s2 <= end) {
			tmp[i++] = p[s2++];
	}
	while (s1 <= mid) {
			tmp[i++] = p[s1++];
	}
	memcpy(p + begin, tmp, sizeof(int) * (end - begin + 1));
}
void Print(int* p, int size)
{
	for (int i = 0; i < size; i++) {
		printf("%d ", p[i]);
	}
	printf("\n");
}
void test()
{
	int arr[]={ 4,6,1,-2,-4,-6,9,0,5,3,2,7,-5,8,11,10,24 };
	int sz = sizeof(arr) / sizeof(int);
	Print(arr, sz);
	int* p = new int[sz];
	MergeSort(arr, p,0, sz-1);
	Print(arr, sz);
}
int main() {
	test();

	return 0;
}